package swardToOffer.struct_5_stack_or_queue;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author ChanZany
 * @Date 2021/5/20 9:47
 * @Version 1.0
 面试题9：用两个栈实现队列
 题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail
 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
 思路：
 appendTail可以直接push到stack1里
 deleteHead可以从stack1把弹出的元素放入stack2，然后最后一个待删除的头结点就不放入了
 */

class MyQueue<T>{
    private Stack<T> stack1;
    private Stack<T> stack2;

    MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(T ele){
        stack1.push(ele);
    }

    public T deleteHead(){
        while (!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
       return stack2.pop();
    }

}
class MyStack<T>{
    private Queue<T> queue1;
    private Queue<T> queue2;
    public MyStack(){
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    public void push(T ele){
        //queue1插入
        queue1.offer(ele);
    }

    //弹出头结点
    public T pop(){
        if (queue1.size()==0 && queue2.size()>0){
            Queue<T> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }
        while (queue1.size()>1){
            queue2.offer(queue1.remove());
        }
        return queue1.remove();
    }
}

public class QueueImplByStack {
    static void test2(){
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
    }
    static void test1(){
        MyQueue<Integer> queue = new MyQueue<>();
        queue.appendTail(1);
        queue.appendTail(2);
        queue.appendTail(3);
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
        System.out.println(queue.deleteHead());
    }
    public static void main(String[] args) {
        test2();
    }
}
